/**
////////////////////////////////////////////////////////////////////////////////
//                                                                            // 
//  Copyright (c) 2013 Santiago Benito Rebollo. Eclipse Public License - v 1.0//
//  @author Santiago Benito Rebollo.                                          // 
//  santiago.benito.rebollo@gmail.com                                         //
//                                                                            //  
////////////////////////////////////////////////////////////////////////////////
//                                                                            //
// THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS ECLIPSE PUBLIC// 
// LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM//
// CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT.                      //
//                                                                            //
// A Contributor may choose to distribute the Program in object code form     //
// under its own license agreement, provided that:                            //
//                                                                            //
// a) it complies with the terms and conditions of this Agreement; and        //
// b) its license agreement:                                                  //
//                                                                            //
// i) effectively disclaims on behalf of all Contributors all warranties and  //
// conditions, express and implied, including warranties or conditions of     //  
// title and non-infringement, and implied warranties or conditions of        //
// merchantability and fitness for a particular purpose;                      //
// ii) effectively excludes on behalf of all Contributors all liability for   //
// damages, including direct, indirect, special, incidental and consequential //
// damages, such as lost profits;                                             //
// iii) states that any provisions which differ from this Agreement are       //
// offered by that Contributor alone and not by any other party; and          //
// iv) states that source code for the Program is available from such         //
// Contributor, and informs licensees how to obtain it in a reasonable        //
// manner on or through a medium customarily used for software exchange.      //
//                                                                            //
////////////////////////////////////////////////////////////////////////////////
 */

/**
 * This class is used for compute the kruskal algorithm
 * and build the graph that can be used in algorithms for build the
 * minimum tree
 *
 * @author Santiago Benito Rebollo
 * @author santiago.benito.rebollo@gmail.com
 */
package com.chago.fastrecado;

import java.util.TreeSet;
import java.util.Vector;
import java.util.HashSet;

/**
 * This is an inner class Edge only for computing purpose
 * 
 * @param none
 * @throws none Exception
 * @pre $none
 * @post $none
*/     
class Edge implements Comparable<Edge>
{
    String vertexA, vertexB;
    double weight;

	/**
     * This is the main constructor
     * 
     * @param String vertexA, String vertexB, double weight
     * @throws none Exception
     * @pre $vertexA!=null
     * @pre $vertexB!=null
     * 
     * @post $none
   */     
    public Edge(String vertexA, String vertexB, double weight)
    {
        this.vertexA = vertexA;
        this.vertexB = vertexB;
        this.weight = weight;
    }
    
	/**
     * This is the get method for vertexA name;
     * 
     * @param none
     * @throws none Exception
     * @pre none
     * @post $none
	*/
    public String getVertexA()
    {
        return vertexA;
    }

	/**
     * This is the get method for vertexB name;
     * 
     * @param none
     * @throws none Exception
     * @pre none
     * @post $none
	*/    
    public String getVertexB()
    {
        return vertexB;
    }

	/**
     * This is the get method for weigth of edge
     * 
     * @param none
     * @throws none Exception
     * @pre none
     * @post $none
	*/        
    public double getWeight()
    {
        return weight;
    }

    /**
     * This is the toString object inherit from Object. Only for tracing purpose
     * 
     * @param none
     * @throws none Exception
     * @pre none
     * @post $none
	*/        
    @Override
    public String toString()
    {
        return "(" + vertexA + ", " + vertexB + ") : Weight = " + weight;
    }

	/**
	* This method overwrite implements the compareTo method of the interface Comparable
	* 
	* @param  Arista a
	* @return int
	* @throws none
	* @pre a!= null
	* @post $none
	*/	
    public int compareTo(Edge edge)
    {
        //== is not compared so that duplicate values are not eliminated.
        return (this.weight < edge.weight) ? -1: 1;
    }
}// end of Edge class

/**
 * This class is used for compute the kruskal algorithm
 * and build the graph that can be used in algorithms for build the
 * minimum tree
 *
 * @author Santiago Benito Rebollo
 * @author santiago.benito.rebollo@gmail.com
 */
class Kruskal
{
    Vector<HashSet<String>> vertexGroups = new Vector<HashSet<String>>();
    TreeSet<Edge> kruskalEdges = new TreeSet<Edge>();

	/**
	* This method return the Edges of the kruskal tree
	* 
	* @param  none
	* @return TreeSet
	* @throws none
	* @pre $none
	* @post $none
	*/	
    public TreeSet<Edge> getEdges()
    {
        return kruskalEdges;
    }

	/**
	* This method return the Vertex group for the vertex argued
	* 
	* @param  String vertex
	* @return HashSet
	* @throws none
	* @pre vertex!= null
	* @post $none
	*/	
    HashSet<String> getVertexGroup(String vertex)
    {
        for (HashSet<String> vertexGroup : vertexGroups) {
            if (vertexGroup.contains(vertex)) {
                return vertexGroup;
            }
        }
        return null;
    }

	/**
	* This is the more important method because it inserts the edge in the correct set of edges
	* 
	* @param  Edge edge
	* @return none
	* @throws none
	* @pre edge!= null
	* @post $none
	*/	
    public void insertEdge(Edge edge)
    {
        String vertexA = edge.getVertexA();
        String vertexB = edge.getVertexB();

        HashSet<String> vertexGroupA = getVertexGroup(vertexA);
        HashSet<String> vertexGroupB = getVertexGroup(vertexB);

        if (vertexGroupA == null) {
            kruskalEdges.add(edge);
            if (vertexGroupB == null) {
                HashSet<String> htNewVertexGroup = new HashSet<String>();
                htNewVertexGroup.add(vertexA);
                htNewVertexGroup.add(vertexB);
                vertexGroups.add(htNewVertexGroup);
            }
            else {
                vertexGroupB.add(vertexA);           
            }
        }
        else {
            if (vertexGroupB == null) {
                vertexGroupA.add(vertexB);
                kruskalEdges.add(edge);
            }
            else if (vertexGroupA != vertexGroupB) {
                vertexGroupA.addAll(vertexGroupB);
                vertexGroups.remove(vertexGroupB);
                kruskalEdges.add(edge);
            }
        }
    }
}